Linear programming (LP) and mixed integer programming (MIP) are well known technologies for building optimization applications. An optimization problem is approximated with linear equations (LP) sometimes with integer valued decision variables (MIP). Then the model (set of equations is solved by LP or MIP engine like IBM Ilog CPLEX), which outputs an optimal solution (or near optimal solution in the MIP case), with regard to an objective. IBM, CPLEX and Ilog are trademarks of International Business Machines in the US and/or other countries.
Optimization engines (for instance LP and MIP engines) can provide a solution that has an undesired characteristic even if it is mathematically optimal. Furthermore, a solution proposed by a solving engine is arbitrarily chosen by the engine among all possible ones. Generally a solution is chosen based on algorithmic criteria, or mathematical criteria, unrelated to the semantics of the problem being solved. Moreover, in the LP case, and in lesser measure in the MIP case, a solution is generally extreme (mathematically a vertex in mathematical search space), meaning that LP/MIP algorithms favor solutions using a very small subset of decision variables. Some variables are “artificially unused” if their value is zero, but having a positive value would not degrade the solution quality mathematically they are “in base, but null”).
The prior art addresses the problem of mixing known solutions, but no approach tries to find a solution in the middle of a feasible or optimal space to allow calculate compromise solutions instead of extreme ones.
One simple solution consists in exploring all extreme solutions S1, S2, . . . , Sn, and finding the sum of weighted solutions divided by the weight.
This simple solution has a disadvantage that it includes all of the extreme solutions in the averaging. All these solutions needs to be calculated explicitly which is very time/CPU consuming An extreme solution is also known as a vertex or base solution. Furthermore it takes some time to compute them because of the potentially large number of the extreme solutions.
Another solution using Pareto optimality also uses all of the solution S1, S2, . . . , Sn. This solution uses an explicit (known) list of relevant individual solutions to balance and calculates the solution is a smarter way. This can save some calculation time but requires that a list of the relevant individual solution is already known.
US patent publication 2010/0287073 A1 is titled ‘Method for optimizing a transformation scheme’ discloses including multiple objectives but does not disclose mixing a plurality of optimal solutions.
US patent publication 2009/0271230 A1 is titled ‘Method and system for solving stochastic linear programs with the condition value at risk constraints’. This stochastic MIP method iteratively searches for optimality with respect to risk constraints, but does not mix optimal solutions.
US patent publication 2011/0131167 A1 is titled ‘Linear programming relaxation modification and cut selection in a MIP solution’ uses LP relaxation and cutting planes for pruning the search space, but does not mix optimal solutions.
U.S. patent application Ser. No. 7,346,528 B2 is titled ‘Integrated decision support system for optimizing the training and transition of airline pilots’. The adaptive, dynamic, integrated, and automated optimizer system comprises parameters of a mixed integer programming model that are altered to provide multiple alternative solutions of said mixed integer programming model. This model proposes multiple solutions, but each solution is the optimal solution of a different MIP models (not a unique model), by model parameters alteration. Moreover, those various solutions are not mixed; they are only exposed to the user as is.
US patent publication 2011/0202638-A1 is titled ‘Mixed integer programming model for minimizing leased access network costs’. This discloses an application of regular MIP algorithm to find one (only) solution a MIP problem. The originality is in the model, not the solving approach. The post optimization step does not do mixing solution either.
US patent publication 2002/0156663-A1 is entitled ‘Shipping and transportation optimization system and method’. Here the MIP model is solved by successive LPs, followed by local search. The successive solutions in both cases are not optimal (and moreover are not mixed), and the algorithm stops at first solution satisfying the halting criterion.
US patent publication 2005/0265359-A1 is titled ‘Optimizing switch port assignments’. This is a quadratic MIP model solved by two methods: 1) classical QP w/a branch and bound, 2) an IP approximation of the quadratic term. There are no optimal solutions mixing in this publication.
A solution is needed that avoids explicit calculation of all the extreme solutions and thus avoids unrealistic exploration in this search space.
A solution is needed that requires less processing time.
A solution is needed that does not require external knowledge of the extremes solutions.